package foundation.图论.bfs;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author hang an
 * @since 2025/7/15
 */
public class R407接雨水2 {
    public int trapRainWater(int[][] heightMap) {
        // q[0]:x  q[1]: y   q[2]: 触发水溢出的格子长度
        int res = 0;
        int n = heightMap.length;
        int m = heightMap[0].length;
        int cnt = n * m;
        if (n <= 2 || m <= 2) return res;
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        int[] move = new int[]{-1, 0, 1, 0, -1};
        boolean[][] visited = new boolean[n][m];
        int x, y, w, nx, ny;
        // 先将四周放入
        // 第一行 最后一行
        for (int i = 0; i < m; i++) {
            int[] first = new int[]{0, i, heightMap[0][i]};
            int[] last = new int[]{n - 1, i, heightMap[n - 1][i]};
            visited[0][i] = true;
            visited[n - 1][i] = true;
            queue.add(first);
            queue.add(last);
        }
        //  第一列与最后一列
        for (int i = 1; i < n - 1; i++) {
            int[] first = new int[]{i, 0, heightMap[i][0]};
            int[] last = new int[]{i, m - 1, heightMap[i][m - 1]};
            visited[i][0] = true;
            visited[i][m - 1] = true;
            queue.add(first);
            queue.add(last);
        }
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            x = cur[0];
            y = cur[1];
            w = cur[2];
            // 计算
            res += w - heightMap[x][y];
            for (int i = 0; i < 4; i++) {
                nx = x + move[i];
                ny = y + move[i + 1];
                if (0 < nx && nx < n - 1 && 0 < ny && ny < m - 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny, Integer.max(heightMap[nx][ny], w)});
                }
            }
        }
        return res;
    }
}
